1. Field of the Invention
The present invention concerns wire routing optimization, and particularly relates to wire routing optimization during integrated circuit (IC) design.
2. Description of the Related Art
To perform integrated circuit design in an efficient and relatively quick manner, the design process typically is implemented as a series of discrete steps. The starting point for the physical design step typically is a particular type of circuit description, called a xe2x80x9cnetlistxe2x80x9d. In general, a netlist specifies a number of standard circuit elements, called xe2x80x9ccellsxe2x80x9d, together with interconnections between the cells. More specifically, the netlist specifies interconnections between particular xe2x80x9cpinsxe2x80x9d on the various cells. Each connected group of pins is referred to as a xe2x80x9cnetxe2x80x9d. Based on the input netlist, the physical design step generates information which can be used to fabricate an integrated circuit to implement the specified circuit description.
One sub-step of physical design involves laying out (or placing) the cells on the surface of the integrated circuit chip (or die). After the cells have been so placed, wires are routed between pins on the cells as specified by the input netlist. It should be noted that wire routing refers to the mapping out of the intended paths for each connection, with the actual wires being formed during the fabrication step.
In particular, wires ordinarily are routed on one or more metal layers which are formed on top of a semiconductor substrate of the IC die. Currently, a typical IC die includes 2 to 4 metal layers. However, even more metal layers are contemplated. The routing step ordinarily includes a global routing step and a detailed routing step.
Global routing specifies rough routing paths through different regions of the routing space, such as by using a coarse routing grid. Detailed routing then completes the point-to-point connections between the pins based on the global routing information.
After an initial global routing has been completed, it is typically necessary or desirable to perform routing optimization, such as to re-route wires routed in overly congested regions. One example of such routing optimization is described in U.S. patent application Ser. No. 09/062,246 filed Apr. 17, 1998, titled xe2x80x9cMethod and Apparatus for Coarse Global Routingxe2x80x9d , now U.S. Pat. No. 6,260,183. Application Ser. No. 09/062,246(the ""246 Application) is hereby incorporated herein by reference, as though set forth herein in full.
The method for routing optimization described in the ""246 Application is described as follows. For each net, two quotients are calculated: The length of net""s bounding box divided by the length of the design, and the width of the net""s bounding box divided by the width of the design. The larger of the two is termed the net""s characteristic. This roughly suggests how large a part of design needs to be in order to contain the net""s bounding box. The nets are then ordered in descending order according to this characteristic. The nets with a characteristic larger than xc2xc are routed sequentially. Then, the design is split into four parts, and different processors are given different parts and instructed to route only the nets that are completely contained in the corresponding parts and have a characteristic that is larger than xe2x85x9. Next, the parts are shifted to the right by a quarter of the design""s length and the same operation is followed. The parts are then shifted from their original positions down by a quarter and the routing procedure is repeated. The parts are then shifted from their original positions both down and to the right by a quarter and the routing procedure is repeated. This way all nets with characteristics larger than xe2x85x9 will be routed. Next the design is split into twice smaller parts, the nets of characteristic larger than {fraction (1/16)} are considered and the shifting process is repeated, moving the parts xe2x85x9 instead of xc2xc. At this point, more processors can be included to speed up the routing process. This process is repeated a few times using smaller and smaller parts, and once all the processors are kept busy, all the remaining nets are re-routed.
Thus, in the foregoing routing optimization technique, the largest nets are processed first, and then the chip is divided into progressively smaller parts to accommodate nets of various sizes, with each part being assigned to a different processor. This technique therefore permits re-routing using parallel processing. However, applicants have discovered that the foregoing technique has certain disadvantages which can limit the speed of routing optimization. First, when using the above technique, each net is re-routed as a whole. As a result, a significant amount of processing time often is required in order to re-route very large nets according to this technique. In addition, maximum use of parallel processing can only be attained with the above technique when the lower levels of chip area division are reached.
FIG. 1 illustrates these problems with the foregoing approach. Specifically, FIG. 1 illustrates an integrated circuit chip 1 upon which a net 5 is initially routed. Net 5 consists of pins 7 and interconnection segments 9 between the pins. As shown in FIG. 1, net 5 is larger than a single quadrant of the integrated circuit chip. Accordingly, net 5 is processed in its entirety in the first stage of the foregoing technique, before the chip is divided into smaller parts. As a result, the advantages of parallel processing are not realized when re-routing net 5. Moreover, due to the size of net 5, re-routing it very likely will require a large amount of processing time.
Therefore, a faster method of re-routing nets is desired.
The present invention addresses this need by dividing a surface, such as a surface of an IC chip, into a set of areas and defining boundary pins where nets intersect the boundary areas.
Thus, according to one aspect, the invention is directed to optimization of an initial routing that connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a set of areas, and a boundary pin is defined at each point on a boundary of one of the areas where the boundary of the one of the areas intersects a net. Routing optimization is then performed in at least one of the areas, the routing optimization optimizing the routing among the net pins and the boundary pins within the at least one of the areas.
By virtue of the foregoing arrangement, large nets frequently can be re-routed in smaller portions, which can have the effect of decreasing the amount of time required for routing optimization processing. In addition, use of boundary pins as set forth above generally will permit each area to be processed independently of the others, so as to allow a different processor to process each different area.
The present invention also addresses the foregoing need by independently performing routing optimization in pre-defined areas in a first set, and also independently performing routing optimization in pre-defined areas in a second set, where each of certain pre-defined areas in the first set overlap at least two pre-defined areas in the second set and each of certain pre-defined areas in the second se t overlap at least two pre-defined areas in the first set.
Thus, according to a further aspect, the invention is directed to optimization of an initial routing t hat connects nets on a surface, each of the nets including plural interconnected net pins. The surface is divided into a first set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the first set. The surface is divided into a second set of pre-defined areas, and routing optimization is performed independently in each of the pre-defined areas in the second set. It is a feature of this aspect of the invention that each of plural pre-defined areas in the first set overlaps at least two pre-defined areas in the second set, and each of plural pre-defined areas in the second set overlaps at least two pre-defined areas in the first set.
By virtue of the foregoing arrangement, the present invention can frequently provide adequate routing optimization even in the presence of large nets, and even though routing optimization is performed independently in the pre-defined areas, such as by using parallel processing. In particular, the foregoing arrangement can generally permit re-routing of connections within a larger area than the pre-defined areas in which routing optimization is performed. Moreover, in more particularized aspects, the foregoing arrangement can often permit a flexible tradeoff between speed and quality of results, by merely increasing or decreasing a number of iterations performed.